package _动态规划系列._正则表达;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/31 20:49
 * <p>
 * 功能描述:
 */
public class Summary_0010 {

    public static void main(String[] args) {
        Summary_0010 test = new Summary_0010();
        test.isMatch("aab", "c*a*b*");

    }

    public boolean isMatch(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        //boolean数组默认初始化为false
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[0][0] = true;//dp[i][j] 表示 s 的前 i 个是否能被 p 的前 j 个匹配
        //base case   aab c*a*b*   给二维数组的第一行赋值
        for (int i = 0; i < p.length(); i++) { // here's the p's length, not s's
            if (p.charAt(i) == '*' && dp[0][i - 1]) {
                dp[0][i + 1] = true; // here's y axis should be i+1
            }
        }
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < p.length(); j++) {
                if (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i)) {//如果是任意元素 或者是对于元素匹配
                    dp[i + 1][j + 1] = dp[i][j];
                }
                if (p.charAt(j) == '*') {
                    if (p.charAt(j - 1) != s.charAt(i) && p.charAt(j - 1) != '.') {//如果前一个元素不匹配 且不为任意元素
                        dp[i + 1][j + 1] = dp[i + 1][j - 1];
                    } else {
                        dp[i + 1][j + 1] = (dp[i][j + 1] || dp[i + 1][j] || dp[i + 1][j - 1]);
                            /*
                            dp[i][j] = dp[i-1][j] // 多个字符匹配的情况
                            or dp[i][j] = dp[i][j-1] // 单个字符匹配的情况
                            or dp[i][j] = dp[i][j-2] // 没有匹配的情况
                             */
                    }
                }
            }
        }
        return dp[s.length()][p.length()];
    }


    public boolean isMatch1(String s, String p) {
        if (s == null || p == null) {
            return false;
        }

        int m = s.length();
        int n = p.length();
        // dp[i][j] 表示 s 的前 i 个是否能被 p 的前 j 个匹配
        boolean[][] dp = new boolean[m + 1][n + 1];

        dp[0][0] = true;  //这个base case是很显然的

        /*
         * 1.下面的base case就不太好弄了。这里的base case明显就是初始化dp table第一行。
         * 2.为什么第一列不初始化呢？因为第一列dp[i][0]的意思是  p串为空，那么必然是匹配不了的,
         * 所以全为false。Java的boolean数组已经默认这样初始化了
         * 3.初始化的时候 假设 s=""  p="c*a*b*"
         * 4."" 和p的匹配关系初始化，a*a*a*a*a*这种能够匹配空串，其他的是都是false。
         * 奇数位不管什么字符都是false，偶数位为* 时则: dp[0][i] = dp[0][i - 2]
         */
        for (int j = 0; j < n; j++) {
            if (p.charAt(j) == '*' && dp[0][j - 1] == true) {
                dp[0][j + 1] = true;
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
                    dp[i + 1][j + 1] = dp[i][j];
                }
                if (p.charAt(j) == '*') {
                    if (p.charAt(j - 1) == s.charAt(i) || p.charAt(j - 1) == '.') {
                        dp[i + 1][j + 1] = (dp[i][j + 1]  //匹配多个  qqbb qqb*
                                || dp[i + 1][j]  //匹配一个  qqb qqb*
                                || dp[i + 1][j - 1]);  //不匹配  qqb qqbb*
                    } else {
                        dp[i + 1][j + 1] = dp[i + 1][j - 1];
                    }
                }
            }
        }
        return dp[m][n];
    }
}
